1. Field of the Invention
The invention relates to the field of computer systems. More specifically, the invention relates to the area of memory management.
2. Background Information
Memory addressing schemes often use a technique called paging to implement virtual memory. When using paging, the virtual address space (i.e., the address space generated by either the execution unit of a processor or by the execution unit in conjunction with a segmentation unit a processor) is divided into fix sized blocks called pages, each of which can be mapped onto any of the physical addresses (i.e., the addresses that correspond to hardware memory locations) available on the system. In a typical computer system, a memory management unit determines and maintains, according to a paging algorithm, the current mappings for the virtual to physical addresses using page tables. Upon receiving a virtual address from the execution unit of a processor, the memory management unit translates the virtual address into its corresponding physical address using the page tables.
In one implementation, the page tables are accessed using a page directory. Each virtual address includes three portions: a directory portion, a table portion, and an offset portion. The directory portion is an offset into the page directory, which is held in main memory. The base-address of this page directory is held in a control register. The processor adds the base-address to the directory portion to get the address of the appropriate directory entry. Each directory entry stores the base-address of a page table, which is also held in main memory. The processor finds the address of the appropriate page-table entry by adding the table portion (from the virtual address) to the page-table-base address (from the directory entry). Each page-table entry stores the base-address of a page-frame. Finally, the processor finds the virtual address' corresponding physical address by adding the offset portion (from the virtual address) to the page-frame-base address (from the page-table entry).
Since the page tables are in main memory, accessing them is time consuming. To speed up the paging translations, certain of the translations are stored in a translation look-aside buffer or TLB (a faster memory that is preferably located on the processor). Upon generating a virtual address requiring translation, the memory management unit first searches for the translation in the TLB before accessing the paging algorithm and page tables.
Each translation stored in the TLB typically contains a virtual address portion, a physical address portion, and an attribute portion. To determine if a translation corresponds to a virtual address, the directory and table portions of the virtual address are compared to the virtual address portion of the translation. If they do not match, the translation does not correspond to the virtual address. However, if they match, the translation corresponds to the virtual address. If the translation corresponds to the virtual address, the physical address portion of the translation is concatenated with the offset portion of the virtual address to generate the virtual address' corresponding physical address. Further explanation of paging schemes is provided in Shanley, Tom and Anderson, Don, ISA System Architecture, published by MindShare, Inc., 1993.
One method for implementing a memory management unit is to hardwire the paging translation algorithm in the processor. A second method for implementing a memory management unit is to allow the paging translation algorithm to be determined by the operating system (commonly referred to as software TLB fills). According to this second method, if during the execution of a process a virtual address is generated whose translation is not installed in the TLB, a TLB miss fault is generated. In response to the TLB miss fault, the processor interrupts the execution of the current process, stores the interrupted process' execution environment (i.e., the information necessary to resume execution of the interrupted process), and invokes an operating system handler (referred to herein as the TLB handler) to determine the paging translation. The TLB handler determines the translation and causes the processor to install it in the TLB. Typically, the installation of translations into the TLB is performed using TLB installation registers located on the processor--i.e., the TLB handler stores the translation in the TLB installation registers and instructs the processor to install the translation in the TLB. These registers often include a virtual address installation register, a physical address installation register, and an attribute installation register for storing the virtual address portion, physical address portion, and attribute portion, respectively, of the translation to be installed in the TLB. Upon completion of the TLB handler, the processor resumes execution of the interrupted process.
TLB fills occur at a much higher rate than other types of events (e.g., exceptions, interrupts, operating system calls, etc.). This high rate of occurrence makes it desirable that the software TLB fills handler(s) be as streamlined as possible.